#pragma once

#include "iostream"
#include "vector"
#include "algorithm"
#include "TypeDefin.h"
using namespace std;
/*HJJ QQ479287006
 *给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

 

示例 1:


输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:

输入: preorder = [-1], inorder = [-1]
输出: [-1]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */

TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    if (preorder.size()==0)
        return nullptr;
    auto midVal= preorder[0];//获取根节点
    TreeNode* root =new TreeNode(midVal);

    if (preorder.size()==0)
        return root;


   int index=0;

    for (int i = 0; i <inorder.size() ; ++i) {
        if (inorder[i]==midVal)
            index=i;
    }

    index++;
    vector<int> preorderSubLeft(preorder.begin()+1,preorder.begin()+index);

    vector<int> preorderSubRight(preorder.begin()+index,preorder.end());


    vector<int> inorderSubLeft(inorder.begin(),inorder.begin()+index-1);

    vector<int> inorderSubRight(inorder.begin()+index,inorder.end());

    root->left=buildTree(preorderSubLeft,inorderSubLeft);
    root->right=buildTree(preorderSubRight,inorderSubRight);

    return root;


}